package LeetCode;

/**
 * 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 思路：找到倒数第n+1个[倒数第n个的前驱]节点【剑指offer-22】，删除
 */
public class offerII_021 {
    public ListNode removeNthFromEnd(ListNode head,int n){
        ListNode node=head;
        for (int i = 0; i < n; i++) {
            if(node==null){
                System.err.println("k illegal!");
                return head;
            }
            node=node.next;
        }
        ListNode dummyHead=new ListNode(-5);
        dummyHead.next=head;
        ListNode fast=dummyHead;
        ListNode slow=dummyHead;
        for (int i = 0; i < n+1; i++) {
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        //此时slow是倒数n+1个节点，也是倒数第n个节点的前驱
        if(slow==null){
            return dummyHead.next;
        }else {
            slow.next = slow.next.next;
        }
        return dummyHead.next;
    }
}
